import unittest

'''
Min binary heap. Use '<' operator for comparison.
Don't allow None values. Priority can be negative, zero or positive.


Store elements as a tuple:   (priority, value)
For example:
[(2, 'two'), (4, 'four'), (5, 'five'), (10, 'ten')] etc.
'''
class MinHeap(object):

    def __init__(self, initialSize = 16):
        if initialSize < 0:
            initialSize = 16
        self.__size = 0
        self.__data = [None] * initialSize

    '''
    Time: O(1)
    Space: O(1)
    '''
    @property
    def empty(self):
        return self.__size == 0

    '''
    Time: O(1)
    Space: O(1)
    '''
    @property
    def size(self):
        return self.__size

    @property
    def data(self):
        return self.__data

    def min(self):
        if self.__size == 0:
            raise ValueError("Can't get min element: heap is empty")
        return self.data[0][1]

    '''
    Time: O(lgN)
    Space: O(1)
    '''
    def pop(self):
        if self.empty:
            raise ValueError("Heap is empty")

        retValue = self.data[0]

        self.__size -= 1
        self.data[0] = self.data[self.__size]
        self.data[self.__size] = None

        self.__fixDown(0)
        return retValue[1]

    '''
    Takes linear time in worse case.
    Time: O(N)
    Space: O(1)
    '''
    def changePriority(self, value, newPriority):
        if value == None:
            raise ValueError("Can't change priority for None value")

        # finding value takes O(N) in worse case

        indexToChange = -1

        for index in range(self.__size):
            if self.__data[index][1] == value:
                indexToChange = index
                break

        # value found, change priority
        if indexToChange > 0:

            prevEntry = self.__data[indexToChange]
            self.__data[indexToChange] = (newPriority, value)

            if prevEntry[0] < newPriority:
                self.__fixDown(indexToChange)
            elif prevEntry[0] > newPriority:
                self.__fixUp(indexToChange)

            return True

        # value not found 
        return False


    '''
    N - current heap size
    M - other heap size

    Performance would be better if we add all elements to bigger heap.

    MIN = min(N, M)
    MAX = max(N, m)

    Time: O(lg MAX * MIN)
    Space: O(1)
    '''
    def union(self, heap):

        if heap == None:
            raise ValueError("Can't union with None heap")

        # copy data from another 'heap', this prevents aliasing and data corruption
        otherData = heap.__data[0:heap.__size]

        # choose the bigger heap to add elements to
        if self.__size < len(otherData):
            self.__data, otherData = otherData, self.__data

        otherDataLen = len(otherData)

        for index in range(otherDataLen):
            self.__data[self.__size] = otherData[index]
            self.__size += 1
            self.__fixUp(self.__size-1)

    '''
    Time: O(lgN)
    Space: O(1)
    '''
    def add(self, priority, value):

        if value == None:
            raise ValueError("Can't store None value in a heap")

        entry = (priority, value)

        if self.__size < len(self.data):
            self.data[self.__size] = entry
        else:
            self.data.append( entry )
            
        self.__fixUp(self.__size)
        self.__size += 1

    def __len__(self):
        return self.__size

    def __str__(self):
        strValue = ""

        if self.__size > 0:
            strValue = str(self.__data[0])

        for index in range(1, self.__size):
            strValue += ", " + str(self.__data[index])
            
        return strValue

    def __repr__(self):

        strValue = "size = " + str(self.__size) + ", ["

        if self.__size > 0:
            strValue += str(self.__data[0])

        for index in range(1, self.__size):
            strValue += ", " + str(self.__data[index])

        strValue += "]"

        return strValue

    def __parentIndex(self, index):
        return int((index-1) / 2)

    def __leftChildIndex(self, index):
        return 2*index + 1

    def __rightChildIndex(self, index):
        return 2 * index + 2

    def __fixDown(self, index):

        minIndex = -1

        while index != minIndex:

            minIndex = index

            leftChild = self.__leftChildIndex(index)

            if leftChild >= self.__size:
                break

            if self.data[leftChild][0] < self.data[minIndex][0]:
                minIndex = leftChild

            rightChild = self.__rightChildIndex(index)

            if rightChild < self.__size and self.data[rightChild][0] < self.data[minIndex][0]:
                minIndex = rightChild

            if minIndex != index:
                self.data[index], self.data[minIndex] = self.data[minIndex], self.data[index]
                index = minIndex


    def __fixUp(self, index):

        parentIndex = self.__parentIndex(index)
        
        while self.__data[parentIndex][0] > self.__data[index][0]:
            self.__data[parentIndex], self.__data[index] = self.__data[index], self.__data[parentIndex]
            index = parentIndex
            parentIndex = self.__parentIndex(index)



class BinaryHeapTest(unittest.TestCase):

    def setUp(self):

        # heap1 [1, 3, 6, 8]
        self.baseHeap = MinHeap()
        self.baseHeap.add(8, "eight")
        self.baseHeap.add(3, "three")
        self.baseHeap.add(6, "six")
        self.baseHeap.add(1, "one")

    def testReprOperator(self):
        #TODO:
        self.assertEqual( "size = 4, [(1, 'one'), (3, 'three'), (6, 'six'), (8, 'eight')]", repr(self.baseHeap) )

    def testStrOperator(self):
        self.assertEqual( "(1, 'one'), (3, 'three'), (6, 'six'), (8, 'eight')", str(self.baseHeap) )

    def testLenOperator(self):
        self.assertEqual( 4, len(self.baseHeap) )

    def testChangePriority(self):
        # heap1 [1, 3, 6, 8]
        self.assertTrue( self.baseHeap.changePriority("eight", 2) )

        # heap1 [1, 2, 6 ,3]
        self.assertContentEqual( [(1, "one"), (2, "eight"), (6, "six"), (3, "three")], self.baseHeap  )

    def testChangePriorityForNotExistedValue(self):
        self.assertFalse( self.baseHeap.changePriority("five", 2) )
        self.assertContentEqual( [(1, "one"), (3, "three"), (6, "six"), (8, "eight")], self.baseHeap  )


    def testAdd2(self):
        heap = MinHeap()
        heap.add(8, "eight")
        heap.add(3, "three")
        heap.add(6, "six")
        heap.add(1, "one")

        # heap1 [1, 3, 6, 8]
        self.assertContentEqual( [(1, "one"), (3, "three"), (6, "six"), (8, "eight")], heap  )

    def testUnion(self):
        heap1 = MinHeap()
        heap1.add(10, "ten")
        heap1.add(5, "five")
        heap1.add(2, "two")
        heap1.add(4, "four")

        heap2 = MinHeap()
        heap2.add(8, "eight")
        heap2.add(3, "three")
        heap2.add(6, "six")
        heap2.add(1, "one")

        # heap1 [2, 4, 5, 10]
        self.assertContentEqual( [(2, "two"), (4, "four"), (5, "five"), (10, "ten")], heap1 )

        # heap2 [1, 3, 6, 8]
        self.assertContentEqual( [(1, "one"), (3, "three"), (6, "six"), (8, "eight")], heap2 )

        heap1.union(heap2)
        self.assertContentEqual( [(1, "one"), (2, "two"), (3, "three"), (8, "eight"), (4, "four"), (5, "five"), (6, "six"), (10, "ten")], heap1 )

        # heap2 shouldn't be changed
        self.assertContentEqual( [(1, "one"), (3, "three"), (6, "six"), (8, "eight")], heap2 )
        

    def testAdd(self):
        heap = MinHeap()

        self.assertEqual( 0, heap.size )
        self.assertTrue( heap.empty )

        heap.add(10, "ten")
        self.assertEqual( 1, heap.size )
        self.assertFalse( heap.empty )
        self.assertContentEqual([(10, "ten")], heap)

        heap.add(5, "five")
        self.assertEqual( 2, heap.size )
        self.assertFalse( heap.empty )
        self.assertContentEqual( [(5, "five"),(10, "ten")], heap )

        heap.add(2, "two")
        self.assertEqual( 3, heap.size )
        self.assertFalse( heap.empty )
        self.assertContentEqual( [(2, "two"), (10, "ten"),(5, "five")], heap )

        heap.add(4, "four")
        self.assertEqual( 4, heap.size )
        self.assertFalse( heap.empty )
        self.assertContentEqual( [(2, "two"), (4, "four"), (5, "five"), (10, "ten")], heap )


    def testPopAndMin(self):
        heap = MinHeap()
        heap.add(10, "ten")
        heap.add(5, "five")
        heap.add(2, "two")
        heap.add(4, "four")

        # heap [2, 4, 5, 10]
        self.assertEqual( "two", heap.min() )
        self.assertEqual( "two", heap.pop())
        self.assertEqual( 3, heap.size )
        self.assertFalse( heap.empty )
        self.assertContentEqual( [(4, "four"), (10, "ten"), (5, "five")], heap )

        # heap [4, 10, 5]
        self.assertEqual( "four", heap.min() )
        self.assertEqual("four", heap.pop())
        self.assertEqual( 2, heap.size )
        self.assertFalse( heap.empty )
        self.assertContentEqual( [(5, "five"), (10, "ten")], heap )

        # heap [ 5, 10 ]
        self.assertEqual( "five", heap.min() )
        self.assertEqual( "five", heap.pop())
        self.assertEqual( 1, heap.size )
        self.assertFalse( heap.empty )
        self.assertContentEqual( [ (10, "ten")], heap )

        # heap [ 10 ]
        self.assertEqual( "ten", heap.min() )
        self.assertEqual( "ten", heap.pop())
        self.assertEqual( 0, heap.size )
        self.assertTrue( heap.empty )
        self.assertContentEqual( [], heap )


    def assertContentEqual(self, expected, heap):
        lastIndex = 0

        for value in heap.data:
            if value == None:
                break
            lastIndex += 1

        self.assertEqual( expected, heap.data[0:lastIndex])



if __name__ == "__main__":
    unittest.main(BinaryHeapTest)

  